//You are given a doubly linked list and an array of references to nodes on the linked list. How many "blocks" are there present in the linked list? 
//
//A "block" is defined as a group of nodes on the list with references directed at them and adjacent to eachother. 
//
//For example 
//
//[node #0] -><-[node#1] -><-[node#2] -><-[node#3] 
//
//node[] nodes = {ref_to_node#0, ref_to_node#2, ref_to_node#3}; 
//
//Is two blocks because the first block is at node #0. 
//Node #1 has no incomming reference. Node #2 and Node #3 have references are are adjacent so it's just one block. 

#include <forward_list>
#include <vector>
#include <unordered_set>
#include <memory>
#include <iostream>

struct Node{
	int m_id;
	Node( int id ) : m_id(id) {}
};

int num_blocks(const std::forward_list<std::shared_ptr<Node> >& list, const std::vector<std::shared_ptr<Node> > & vec){
	std::unordered_set<std::shared_ptr<Node> > table;
	int count = 0;
	bool prev = false, curr;
	for ( int i = 0; i < vec.size(); ++i )
		table.insert(vec[i]);
	for ( std::forward_list<std::shared_ptr<Node> >::const_iterator iter = list.begin(); iter != list.end(); ++iter) {
		curr = table.find(*iter) != table.end();
		if (prev == false && curr == true)
			++count;
		prev = curr;
	}
	return count;
}

void test_num_blocks(){
	std::shared_ptr<Node> n0(new Node(0));
	std::shared_ptr<Node> n1(new Node(1));
	std::shared_ptr<Node> n2(new Node(2));
	std::shared_ptr<Node> n3(new Node(3));
	std::shared_ptr<Node> n4(new Node(4));
	std::forward_list<std::shared_ptr<Node> > list;
	list.push_front(n4);
	list.push_front(n3);
	list.push_front(n2);
	list.push_front(n1);
	list.push_front(n0);

	std::vector<std::shared_ptr<Node> > vec(3);
	vec[0] = n0;
	vec[1] = n3;
	vec[2] = n4;

	std::cout << "num of blocks: " << num_blocks(list,vec) << std::endl;

}